package algorithm.t202112;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/12/5 10:01
 * @description :6道
 * 头晕的一天，KMP算法确实有点意思，还需要慢慢消化啊，每一天都变强一点，时间还有，前提是不浪费的情况下，每天都要做到最好，从9月4号停单那天开始，我已经在
图书馆从到到晚这个状态3个月了，一转眼大四上半学期也马上就要结束了，作为学生时代的最后几门课程也要结课了，再记录一下（星期一12人工智能，星期二34嵌入式系统开发，
星期三没课，星期四34计算机专业英语，星期五34计算机体系结构）最后的课表，唉，这里面只有人工智能是考试课，其他都是考察课。马上就是最后的考试，看样子，大学四年
不挂科应该是可以实现了（可惜没有拿到过奖学金），接下来得花点时间准备毕业实习报告，然后就是去寒假实习，今年的寒假注定是忙碌的，或者说，以后的寒假都
是忙碌的（没有学生这个身份，就基本没有寒暑假这个概念了），唉，时间在走，我也在长大。现在做的一切都是为了明年春招，努力，奋斗！
 * persevere to last
 * 2021.12.5
 * 李红磊
 * 2021年12月5日21:08:59
 */
public class t20211205 {

    //372.超级次方
    public int superPow(int a, int[] b) {
        return 0;
    }

    private int qpow(int a, int b) {
        if (b == 0) return 1;
        if ((b & 1) == 1) return qpow(a, b - 1) * a;
        else {
            int temp = qpow(a, b / 2);
            return temp * temp;
        }

    }

    //638.大礼包
    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        return 0;
    }

    //226.翻转二叉树
    public TreeNode invertTree(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) return root;
        TreeNode tem = root.left;
        root.left = root.right;
        root.right = tem;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    public List<Integer> getRow(int rowIndex) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        ArrayList<Integer> first_row = new ArrayList() {{
            add(1);
        }};
        result.add(first_row);
        if (rowIndex == 0) return first_row;

        for (int i = 1; i <= rowIndex; i++) {
            ArrayList<Integer> tem = new ArrayList() {{
                add(1);
            }};
            for (int j = 1; j < i; j++) {
                tem.add(result.get(i - 1).get(j - 1) + result.get(i - 1).get(j));
            }
            tem.add(1);
            if (i == rowIndex) return new ArrayList<>(tem);
            result.add(new ArrayList<>(tem));

        }

        return null;

    }

    //28.实现strStr()
    public int strStr2(String haystack, String needle) {
        char first = needle.charAt(0);
        int len = needle.length();
        int idx = 1;
        for (int i = 0; i < haystack.length(); i++) {

            if (haystack.charAt(i) == first) {
                boolean flag = true;
                for (int j = i + 1; j < haystack.length(); j++) {

                    if (haystack.charAt(j) != needle.charAt(idx++)) {
                        flag = false;
                        idx = 0;
                        break;
                    }
                    if (idx == len) return i;
                }
                if (flag) return i;
                continue;
            }

        }
        return -1;
    }

    public void getNext(int[] next, String s) {
        int j = -1;
        next[0] = j;
        for (int i = 1; i < s.length(); i++) {
            while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {
                j = next[j];
            }

            if (s.charAt(i) == s.charAt(j + 1)) {
                j++;
            }
            next[i] = j;
        }
    }

    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) {
            return 0;
        }

        int[] next = new int[needle.length()];
        getNext(next, needle);
        int j = -1;
        for (int i = 0; i < haystack.length(); i++) {
            while (j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)) {
                j = next[j];
            }
            if (haystack.charAt(i) == needle.charAt(j + 1)) {
                j++;
            }
            if (j == needle.length() - 1) {
                return (i - needle.length() + 1);
            }
        }

        return -1;
    }

    //524.通过删除字母到字典里最长单词
    public String findLongestWord(String s, List<String> dictionary) {
        Collections.sort(dictionary, (a, b) -> {
            if (a.length() == b.length()) return a.compareTo(b);
            return b.length() - a.length();
        });
        int s_len = s.length();
        for (String element : dictionary) {
            int len = element.length();
            int i = 0, j = 0;
            for (; i < s_len && j < len; ) {
                if (s.charAt(i) == element.charAt(j)) j++;
                i++;
            }
            if (j == len) return element;
        }

        return "";
    }

    //1392.最长快乐前缀  KMP的前缀表
    public String longestPrefix(String s) {
        if (s.length() == 1) return "";
        int len = s.length();
        int[] next = new int[len];
        int j = -1;
        next[0] = j;

        for (int i = 1; i < len; i++) {
            while (j >= 0 && s.charAt(j + 1) != s.charAt(i)) j = next[j];

            if (s.charAt(j + 1) == s.charAt(i)) j++;

            next[i] = j;
        }

        return s.substring(0, j + 1);
    }

    public static void main(String[] args) {
        t20211205 t20211205 = new t20211205();
        t20211205.longestPrefix("cbcbcba");

    }

}
